#include <bits/stdc++.h>
#define ll long long
using namespace std;

int T;
int n,m;
set<int>s[25];
int ans,tag[25],vis[25],c;

void ddfs(int u){
    vis[u]=1;c++;
    for(auto v:s[u]) if(!vis[v]) ddfs(v);
}

inline bool check(){
    int pp=0;
    for(int i=1;i<=n;i++) if(!tag[i]) pp++;
    // cout<<"hel\n";
    // for(int i=1;i<=n;i++) cout<<i<<' '<<s[i].size()<<"\n";
    // puts("");
    for(int i=1;i<=n;i++) if(!tag[i] and s[i].size()!=1) return 0;
    // cout<<"mother\n";
    for(int i=1;i<=n;i++){
        if(!tag[i]){
            memset(vis,0,sizeof vis);
            c=0;
            ddfs(i);
            if(c==pp) return 1;
            return 0;
        }
    }
    return 0;
}
void dfs(int p){
    if(check()){
        ans=min(ans,p);
        return ;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j){
                if(!tag[i] and !tag[j]){
                    tag[j]=1;
                    set<int>f[n+1];
                    for(int k=1;k<=n;k++) f[k]=s[k];
                    for(auto k:s[j]) s[i].insert(k);
                    for(int k=1;k<=n;k++) if(s[k].find(j)!=s[k].end()) s[k].erase(j),s[k].insert(i);
                    s[j].clear();
                    dfs(p+1);
                    tag[j]=0;
                    for(int k=1;k<=n;k++) s[k]=f[k];
                }
            }
        }
    }
}

int main(){
    freopen("circ.in","r",stdin);
    freopen("circ.out","w",stdout);
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        ans=n-1;
        for(int i=1;i<=n;i++) s[i].clear();
        for(int i=1;i<=m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            u++,v++;
            s[u].insert(v);
        }
        dfs(0);
        printf("%d\n",ans);
    }

    // system("pause");
    return 0;
}
/*
4
3 4
0 1
1 2
2 0
0 1
3 5
0 0
1 2
2 0
0 1
0 1
4 2
0 1
2 3
6 6
0 2
1 5
3 0
4 0
1 4
5 0

5
5 4
4 1
1 3
4 2
0 3
*/